The present invention relates generally to template matching for an image.
Referring to FIG. 1, template matching is a commonly used technique in order to recognize content in an image. The template matching technique includes a given target object in a model image, automatically finding the position, orientation, and scaling of the target object in input images. Generally, the input images undergo geometric transforms (rotation, zoom, etc) and photometric changes (brightness/contrast changes, blur, noise, etc). In the context of template matching, the relevant characteristics of the target object in the model image may be assumed to be known before the template matching to the target image is performed. Such characteristics of the target object may be extracted, modeled, and learned previously in a manner that may be considered “off-line,” while the matching of those characteristics to the input image may be considered “on-line.”
One of the template matching techniques includes feature point based template matching which achieves good matching accuracy. Feature point based template matching extracts object discriminative interesting points and features from the model and the input images. Then those features are matched between the model image and the input image with K-nearest neighbor search or some feature point classification technique. Next a homography transformation is estimated from those matched feature points, which may further be refined.
Feature point based template matching works well when objects contain a sufficient number of interesting feature points. It typically fails to produce a valid homography when the target object in the input or model image contains few or no interesting points (e.g. corners), or the target object is very simple (e.g. target object consists of only edges, like paper clip) or symmetric, or the target object contains repetitive patterns (e.g. machine screw). In these situations, too many ambiguous matches prevents generating a valid homography. To reduce the likelihood of such failure, global information of the object such as edges, contours, or shape may be utilized instead of merely relying on local features.
Another category of template matching is to search the target object by sliding a window of the reference template in a pixel-by-pixel manner, and computing the degree of similarity between them, where the similarity metric is commonly given by correlation or normalized cross correlation. Pixel-by-pixel template matching is very time-consuming and computationally expensive. For an input image of size N×N and the model image of size W×W, the computational complexity is O(W2×N2), given that the object orientation in both the input and model image is coincident. When searching for an object with arbitrary orientation, one technique is to do template matching with the model image rotated in every possible orientation, which makes the matching scheme far more computationally expensive. To reduce the computation time, coarse-to-fine, multi-resolution template matching may be used.
What is desired therefore is a computationally efficient edge based matching technique.
The foregoing and other objectives, features, and advantages of the invention may be more readily understood upon consideration of the following detailed description of the invention, taken in conjunction with the accompanying drawings.